# JZ14 链表中倒数最后k个结点
#
# 描述
# 输入一个长度为n的链表，设链表中的元素的值为a_i，
# 输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
# 如果该链表长度小于k，请返回一个长度为0的链表。
#
# 提示:
# 0 ≤n≤10^5
# 0≤a_i≤10^9
# 0≤k≤10^9
# 示例1
# 输入：
# {1, 2, 3, 4, 5}, 3
# 返回值：
# {3, 4, 5}
# 示例2
# 输入：
# {2}, 8
# 返回值：
# {}

# 核心代码
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
    def FindKthToTail(self , pHead , k ):
        # 辅助栈 / 数组思路差不多
        if not pHead or not k: return None
        stack =[]
        # 压入栈
        # 链表pHead为空，即为结束
        while pHead:
            stack.append(pHead)  # 入栈append()
            pHead = pHead.next
        # 出栈
        # 若该链表长度小于k，返回一个长度为 0 的链表
        if len(stack)<k: return None
        # 倒数k个元素出栈
        tempNode = stack.pop() # 出一个元素
        for i in range(k-1):
            pHead = stack.pop()
            pHead.next = tempNode
            tempNode = pHead
        return tempNode